/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/18 21:58
 */
// 排序数组
    // https://leetcode.cn/problems/sort-an-array/description/
public class Solution912Heapify {
    public int[] sortArray(int[] nums) {
        heapify(nums);
        return nums;
    }
    //堆排序
    // https://blog.csdn.net/qichangjian/article/details/87699215
    public void heapify(int[] nums) {
        // 堆化
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            adjustHeap(nums, i , nums.length);
        }
        // 交换根节点和末尾元素,并重新堆化
        for (int i = nums.length - 1; i > 0; i--) {
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            adjustHeap(nums, 0, i);
        }
    }

    private void adjustHeap(int[] nums, int i, int length) {
        // 先取出当前元素i
        int tmp = nums[i];
        for (int k = i*2+1; k < length; k = k*2 + 1) {
            // 如果左子结点小于右子结点，k指向右子结点
            if (k+1 < length && nums[k] < nums[k + 1]){
                k++;
            }
            //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            if (nums[k] > tmp) {
                nums[i] = nums[k];
                i = k;
            } else {
                break;
            }
        }
        nums[i] = tmp;
    }
}
